package algorithm.linked;

/**
 * @Author: zhenzhong.wang
 * @Date: 10/9/2018 9:20 AM
 */
public class InvertLinkedList {

  /**
   * 遍历方式
   *
   * @param root
   * @return
   */
  public Node invert(Node root) {
    Node preNode = null;
    Node currentNode = root;
    Node headNode = null;

    while (currentNode != null) {
      Node nextNode = currentNode.getNext();
      if (nextNode == null) {
        headNode = currentNode;
      }

      currentNode.setNext(preNode);

      preNode = currentNode;
      currentNode = nextNode;
    }
    return headNode;
  }

  /**
   * 递归实现
   *
   * @return
   */
  public Node invertByRecursion(Node node) {
    if (node == null || node.getNext() == null) {
      return node;
    }

    Node reNode = invertByRecursion(node.getNext());
    node.getNext().setNext(node);
    node.setNext(null);
    return reNode;
  }

}
